/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 17, 2014
 */
package zhoujian.oj.leetcode;

/**
 * @version 1.0
 * @description Given a linked list, determine if it has a cycle in it.
 * 
 *              Follow up: Can you solve it without using extra space?
 */
public class LinkedListCycle {

	private class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public boolean hasCycle(ListNode head) {
		if (head == null)
			return false;
		ListNode pointer1 = head;
		ListNode pointer2 = head;
		while (pointer1 != null && pointer2 != null) {
			pointer1 = pointer1.next;
			pointer2 = pointer2.next;
			if (pointer1 == null || pointer2 == null)
				return false;
			pointer2 = pointer2.next;
			if (pointer1 == pointer2)
				return true;
		}
		return false;
	}

}
